//电话号码的字母组合 力扣17
//回溯法 映射
//改进写法
class Solution {
public:
	string path;
	vector<string> ans;
	//建立数字字符和其所对应字符串的映射关系
	vector<string> stringmap{
		"",    //0
		"",    //1
		"abc", //2
		"def", //3
		"ghi", //4
		"jkl", //5
		"mno", //6
		"pqrs",//7
		"tuv", //8
		"wxyz" //9
	};
	void backtracking(string digits,int index)
	{
		if(path.size() == digits.size())
		{
			ans.push_back(path);
			return;
		}
		//根据映射关系找到数字字符对应的字符串
		int digit = digits[index] - '0';
		string letters = stringmap[digit];
		for(int i = 0; i < letters.size() ; i++)
		{
			path.push_back(letters[i]);  //处理本层
			backtracking(digits,index+1);//递归下一层
			path.pop_back();  //回溯
		}
		
	}
	
	vector<string> letterCombinations(string digits) {
		//对于空数字字符串，需单独处理
		if(digits.size() == 0)
			return {};
		backtracking(digits,0);
		return ans; 
	}
};
